package com.zou.practice.sort;

import com.alibaba.fastjson.JSON;

/**
 * @author zouyaowen
 * @date 2020-09-14
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {13, 3, 2, 9, 8, 7, 11};
        System.out.println(JSON.toJSONString(arr));
        // quickSort(arr, 0, arr.length - 1);
        quickSortSecond(arr, 0, arr.length - 1);
        System.out.println(JSON.toJSONString(arr));
    }

    /**
     * 快速排序
     *
     * @param arr   数组
     * @param left  数组最小索引
     * @param right 数组最大索引
     */
    private static void quickSortSecond(int[] arr, int left, int right) {
        if (left < right) {
            int pivot = arr[left];
            int i = left + 1;
            int j = right;
            while (true) {
                //向右遍历扫描
                while (i <= j && arr[i] <= pivot) {
                    i++;
                }
                //向左遍历扫描
                while (i <= j && arr[j] >= pivot) {
                    j--;
                }
                if (i >= j) {
                    break;
                }
                // 交换数据
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            //把arr[j]和主元交换
            arr[left] = arr[j];
            arr[j] = pivot;
            //递归处理数据
            quickSortSecond(arr, left, j - 1);
            quickSortSecond(arr, j + 1, right);
        }
    }

    /**
     * 快速排序方案一：从左向右遍历
     *
     * @param arr   待排序数组
     * @param left  索引开始位置
     * @param right 索引结束位置
     */
    private static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //获取最后一个元素作为参照数据
            int pivot = arr[right];
            //从左边开始遍历
            int i = left;
            int j = left;
            for (; j < right; j++) {
                if (arr[j] < pivot) {
                    int temp = arr[i];
                    arr[i++] = arr[j];
                    arr[j] = temp;
                }
            }
            arr[right] = arr[i];
            arr[i] = pivot;
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
    }
}
